/*
 * Copyright 2009 ZXing authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 * 
 * 
 * 
 * 
 * 
 * 
 * EXPLANATION
 * 
 * Those methods are extracted from the ZXing Library. Only the accessors 
 * are being changed from private to public.
 * 
 */

package com.google.zxing;

import com.google.zxing.NotFoundException;
import com.google.zxing.ResultPoint;
import com.google.zxing.common.BitMatrix;
import com.google.zxing.common.PerspectiveTransform;
import com.google.zxing.common.detector.MathUtils;

public class HelperMethodsFromZXing {
	/**
	 * <p>
	 * Computes an average estimated module size based on estimated derived from
	 * the positions of the three finder patterns.
	 * </p>
	 */
	public static float calculateModuleSize(ResultPoint topLeft,
			ResultPoint topRight, ResultPoint bottomLeft, BitMatrix image) {
		// Take the average
		return (calculateModuleSizeOneWay(topLeft, topRight, image) + calculateModuleSizeOneWay(
				topLeft, bottomLeft, image)) / 2.0f;
	}

	/**
	 * <p>
	 * Estimates module size based on two finder patterns -- it uses
	 * {@link #sizeOfBlackWhiteBlackRunBothWays(int, int, int, int)} to figure
	 * the width of each, measuring along the axis between their centers.
	 * </p>
	 * 
	 * @return
	 */
	public static float calculateModuleSizeOneWay(ResultPoint pattern,
			ResultPoint otherPattern, BitMatrix image) {
		float moduleSizeEst1 = sizeOfBlackWhiteBlackRunBothWays(
				(int) pattern.getX(), (int) pattern.getY(),
				(int) otherPattern.getX(), (int) otherPattern.getY(), image);
		float moduleSizeEst2 = sizeOfBlackWhiteBlackRunBothWays(
				(int) otherPattern.getX(), (int) otherPattern.getY(),
				(int) pattern.getX(), (int) pattern.getY(), image);
		if (Float.isNaN(moduleSizeEst1)) {
			return moduleSizeEst2 / 7.0f;
		}
		if (Float.isNaN(moduleSizeEst2)) {
			return moduleSizeEst1 / 7.0f;
		}
		// Average them, and divide by 7 since we've counted the width of 3
		// black modules,
		// and 1 white and 1 black module on either side. Ergo, divide sum by
		// 14.
		return (moduleSizeEst1 + moduleSizeEst2) / 14.0f;
	}

	/**
	 * See {@link #sizeOfBlackWhiteBlackRun(int, int, int, int)}; computes the
	 * total width of a finder pattern by looking for a black-white-black run
	 * from the center in the direction of another point (another finder pattern
	 * center), and in the opposite direction too.</p>
	 */
	public static float sizeOfBlackWhiteBlackRunBothWays(int fromX, int fromY,
			int toX, int toY, BitMatrix image) {

		float result = sizeOfBlackWhiteBlackRun(fromX, fromY, toX, toY, image);

		// Now count other way -- don't run off image though of course
		float scale = 1.0f;
		int otherToX = fromX - (toX - fromX);
		if (otherToX < 0) {
			scale = (float) fromX / (float) (fromX - otherToX);
			otherToX = 0;
		} else if (otherToX >= image.getWidth()) {
			scale = (float) (image.getWidth() - 1 - fromX)
					/ (float) (otherToX - fromX);
			otherToX = image.getWidth() - 1;
		}
		int otherToY = (int) (fromY - (toY - fromY) * scale);

		scale = 1.0f;
		if (otherToY < 0) {
			scale = (float) fromY / (float) (fromY - otherToY);
			otherToY = 0;
		} else if (otherToY >= image.getHeight()) {
			scale = (float) (image.getHeight() - 1 - fromY)
					/ (float) (otherToY - fromY);
			otherToY = image.getHeight() - 1;
		}
		otherToX = (int) (fromX + (otherToX - fromX) * scale);

		result += sizeOfBlackWhiteBlackRun(fromX, fromY, otherToX, otherToY,
				image);

		// Middle pixel is double-counted this way; subtract 1
		return result - 1.0f;
	}

	/**
	 * <p>
	 * This method traces a line from a point in the image, in the direction
	 * towards another point. It begins in a black region, and keeps going until
	 * it finds white, then black, then white again. It reports the distance
	 * from the start to this point.
	 * </p>
	 * 
	 * <p>
	 * This is used when figuring out how wide a finder pattern is, when the
	 * finder pattern may be skewed or rotated.
	 * </p>
	 */
	public static float sizeOfBlackWhiteBlackRun(int fromX, int fromY, int toX,
			int toY, BitMatrix image) {
		// Mild variant of Bresenham's algorithm;
		// see http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
		boolean steep = Math.abs(toY - fromY) > Math.abs(toX - fromX);
		if (steep) {
			int temp = fromX;
			fromX = fromY;
			fromY = temp;
			temp = toX;
			toX = toY;
			toY = temp;
		}

		int dx = Math.abs(toX - fromX);
		int dy = Math.abs(toY - fromY);
		int error = -dx >> 1;
		int xstep = fromX < toX ? 1 : -1;
		int ystep = fromY < toY ? 1 : -1;

		// In black pixels, looking for white, first or second time.
		int state = 0;
		// Loop up until x == toX, but not beyond
		int xLimit = toX + xstep;
		for (int x = fromX, y = fromY; x != xLimit; x += xstep) {
			int realX = steep ? y : x;
			int realY = steep ? x : y;

			// Does current pixel mean we have moved white to black or vice
			// versa?
			// Scanning black in state 0,2 and white in state 1, so if we find
			// the wrong
			// color, advance to next state or end if we are in state 2 already
			if ((state == 1) == image.get(realX, realY)) {
				if (state == 2) {
					return MathUtils.distance(x, y, fromX, fromY);
				}
				state++;
			}

			error += dy;
			if (error > 0) {
				if (y == toY) {
					break;
				}
				y += ystep;
				error -= dx;
			}
		}
		// Found black-white-black; give the benefit of the doubt that the next
		// pixel outside the image
		// is "white" so this last point at (toX+xStep,toY) is the right ending.
		// This is really a
		// small approximation; (toX+xStep,toY+yStep) might be really correct.
		// Ignore this.
		if (state == 2) {
			return MathUtils.distance(toX + xstep, toY, fromX, fromY);
		}
		// else we didn't find even black-white-black; no estimate is really
		// possible
		return Float.NaN;
	}

	/**
	 * <p>
	 * Computes the dimension (number of modules on a size) of the QR Code based
	 * on the position of the finder patterns and estimated module size.
	 * </p>
	 */
	public static int computeDimension(ResultPoint topLeft,
			ResultPoint topRight, ResultPoint bottomLeft, float moduleSize)
			throws NotFoundException {
		int tltrCentersDimension = MathUtils.round(ResultPoint.distance(
				topLeft, topRight) / moduleSize);
		int tlblCentersDimension = MathUtils.round(ResultPoint.distance(
				topLeft, bottomLeft) / moduleSize);
		int dimension = ((tltrCentersDimension + tlblCentersDimension) >> 1) + 7;
		switch (dimension & 0x03) { // mod 4
		case 0:
			dimension++;
			break;
		// 1? do nothing
		case 2:
			dimension--;
			break;
		case 3:
			throw NotFoundException.getNotFoundInstance();
		}
		return dimension;
	}

	public static PerspectiveTransform createTransform(ResultPoint topLeft,
			ResultPoint topRight, ResultPoint bottomLeft,
			ResultPoint alignmentPattern, int dimension) {
		float dimMinusThree = (float) dimension - 3.5f;
		float bottomRightX;
		float bottomRightY;
		float sourceBottomRightX;
		float sourceBottomRightY;
		if (alignmentPattern != null) {
			bottomRightX = alignmentPattern.getX();
			bottomRightY = alignmentPattern.getY();
			sourceBottomRightX = dimMinusThree - 3.0f;
			sourceBottomRightY = sourceBottomRightX;
		} else {
			// Don't have an alignment pattern, just make up the bottom-right
			// point
			bottomRightX = (topRight.getX() - topLeft.getX())
					+ bottomLeft.getX();
			bottomRightY = (topRight.getY() - topLeft.getY())
					+ bottomLeft.getY();
			sourceBottomRightX = dimMinusThree;
			sourceBottomRightY = dimMinusThree;
		}

		return PerspectiveTransform.quadrilateralToQuadrilateral(3.5f, 3.5f,
				dimMinusThree, 3.5f, sourceBottomRightX, sourceBottomRightY,
				3.5f, dimMinusThree, topLeft.getX(), topLeft.getY(),
				topRight.getX(), topRight.getY(), bottomRightX, bottomRightY,
				bottomLeft.getX(), bottomLeft.getY());
	}
}